package Z.dailyExercise._1223;

import java.util.*;

public class _1356_根据数字二进制下1的数目排序 {

    /**
     * 自解：本题核心考察的是  计算一个int转为二进制所包含的1
     * 用一个map存储 key存数值 value为包含1的个数--不好比大小
     * 对list比大小的方法 Collection.sort(list,compare接口)
     * * @param arr
     * @return
     */
    public int[] sortByBits(int[] arr) {
        List<Integer> list = new ArrayList<>();
        int[] bit = new int[10001];
        for (int num:arr){
           list.add(num);
            bit[num] = count(num);
        }
        //重写collection接口方法
        Collections.sort(list, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                if (bit[o1] != bit[o2]){
                    return bit[o1]-bit[o2];
                }else {
                    return o1-o2;
                }
            }
        });

        for (int i=0;i<arr.length;i++){
            arr[i] = list.get(i);
        }

        return arr;


    }

    //因为本道题传入的数值非负 所以可以采用数和1相与 =1时 结果++
    //之后右移循环 直到num==0---放弃写法
    //num一直和他-1之后的数字相与 直到最终数字=0 判断循环次数
    public int count(int num){
        int sum = 0;
        while (num>0){
           num = num & (num-1);
           sum++;
        }

        return sum;
    }
}
